#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>

#define _x_ 20;
typedef struct coordinate{
	int x;
	int y;
	int check;
	struct coordinate* next;	
} xy;

xy* startpoint = NULL;

xy* endpoint = NULL;

int check(xy* point){
	int l1,l2;
	l1 = pow(point->x - startpoint->x , 2) + pow(point->y - startpoint->y , 2);
	l1 = sqrt(l1);
	l2 = pow(point->x - endpoint->x , 2) + pow(point->y - endpoint->y , 2);
	l2 = sqrt(l2);
	point->check = 2*l2 + l1;
	return point->check;
}

int* init(){
	int* start = NULL;
	int i = 0 ,n = 0,x = _x_;
	start = (int*)malloc(x * x * sizeof(int));
	memset(start,0,x*x*sizeof(int));
	for(i=0;i<8;++i){
		for(n=0;n<8;++n){
			*(start + (0 * x + 5 + n) + i * x) = 1;
		}
		
	}
	startpoint = (xy*)malloc(sizeof(xy));
	startpoint->x=2;
	startpoint->y=5;
	startpoint->check=0;
	startpoint->next=NULL;
	endpoint = (xy*)malloc(sizeof(xy));
	endpoint->x=19;
	endpoint->y=0;
	endpoint->check=0;
	endpoint->next=NULL;
	return start;
}

int in_list(int x_p,int y_p,xy* list){
	xy* tmp = list;
	while(tmp != NULL){
		if(tmp->x == x_p && tmp->y == y_p){
			return 1;
		}
		tmp = tmp->next;
	}
	return 0;
}

int is_valid(int x_r,int y_r,int* p){
	int x = _x_;
	if(x_r < 0 || y_r <0 ||x_r >= x || y_r >= x || *(p + y_r * x + x_r) == 1){
		return 0;
	}
	return 1;
}

void push(xy* p,xy* list){
	xy* tmp = list;
	while(tmp->next != NULL){
		tmp = tmp->next;
	}
	tmp->next = p;
}

int main(){
	xy* open = NULL;
	xy* closed = NULL;
	int* start = NULL;
	xy* tmp1 = NULL;
	xy* tmp2 = NULL;
	xy* tmp3 = NULL;
	xy* tmp4 = NULL;
	xy* tmp = NULL;
	xy* cur = NULL;
	int x = _x_;
	start = init();
	cur = startpoint;
	int c = 0,n=0;
	open = startpoint;
	closed = (xy*)malloc(sizeof(xy));
	closed->x = -1;
	closed->y = -1;
	closed->next = NULL;
	closed->check = -1;
	
	while(in_list(endpoint->x,endpoint->y,open) != 1){
		if(is_valid(cur->x - 1,cur->y,start) == 1 && in_list(cur->x - 1,cur->y,closed) == 0 && in_list(cur->x - 1,cur->y,open) == 0){
			tmp1 = (xy*)malloc(sizeof(xy));
			tmp1->x = cur->x - 1;
			tmp1->y = cur->y;
			tmp1->check = 0;
			tmp1->next = NULL;
			tmp = tmp1;
			c = check(tmp1);
		}
		if(is_valid(cur->x,cur->y + 1 ,start) == 1 && in_list(cur->x ,cur->y + 1,closed) == 0 && in_list(cur->x ,cur->y + 1,open) == 0){
			tmp2 = (xy*)malloc(sizeof(xy));
			tmp2->x = cur->x;
			tmp2->y = cur->y + 1;
			tmp2->check = 0;
			tmp2->next = NULL;
			if(c > check(tmp2)){
				c = tmp2->check;
			       	push(tmp,closed);
				tmp = tmp2;	
			}else{
				if(tmp == NULL || c == -1){
					tmp = tmp2;
					c = tmp2->check;
				}else{
					push(tmp2,closed);
				}
			}
		}
		if(is_valid(cur->x + 1,cur->y,start) == 1 && in_list(cur->x + 1,cur->y,closed) == 0  && in_list(cur->x + 1,cur->y,open) == 0){
			tmp3 = (xy*)malloc(sizeof(xy));
			tmp3->x = cur->x + 1;
			tmp3->y = cur->y;
			tmp3->check = 0;
			tmp3->next = NULL;
			if(c > check(tmp3)){
				c = tmp3->check;
			       	push(tmp,closed);
				tmp = tmp3;	
			}else{
				if(tmp == NULL || c == -1){
					tmp = tmp3;
					c = tmp3->check;
				}else{
					push(tmp3,closed);
				}
			}
		}
		if(is_valid(cur->x,cur->y - 1,start) == 1 && in_list(cur->x,cur->y - 1,closed) == 0 && in_list(cur->x,cur->y - 1,open) == 0){
			tmp4 = (xy*)malloc(sizeof(xy));
			tmp4->x = cur->x;
			tmp4->y = cur->y - 1;
			tmp4->check = 0;
			tmp4->next = NULL;
			
			if(c > check(tmp4)){
				c = tmp4->check;
			       	push(tmp,closed);
				tmp = tmp4;	
			}else{
				if(tmp == NULL || c == -1){
					tmp = tmp4;
					c = tmp4->check;
				}else{
					push(tmp4,closed);
				}
			}
		}
		if(tmp == NULL){
			return 1;
		}
		push(tmp,open);
		cur = tmp;
		c = -1;
	}
	tmp = open;
	while(tmp != NULL){
		*(start + x * tmp->y + tmp->x) = 2;
		tmp = tmp->next;
	}
	for(c = 0;c < x;++c){
		for(n = 0;n < x;++n){
			printf("%d ",*(start + c * x + n));
		}
		printf("\n");
	}
	return 0;
}
